734C - Anton and Making Potions - CodeForces Solution

binary search dp greedy two pointers *1600

Please click on ads to support us..

Python Code: 

import sys

n, m, k = map(int, input().split())

x, s = map(int, input().split())

a = [x] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))

c = [0] + list(map(int, input().split()))
d = [0] + list(map(int, input().split()))

best = sys.maxsize ** 2 + 1

def search(left):
    l = 0
    r = k
    while l < r:
        m = (l + r + 1) // 2
        if d[m] <= left:
            l = m
        else:
            r = m-1
    return c[l]

for first_spell_i in range(m+1):
    ai = a[first_spell_i]
    bi = b[first_spell_i]
    left = s - bi
    if left < 0:
        continue

    cj = search(left)

        cost = ai * (n-cj)
    best = min(best, cost)

print(best)

C++ Code: 

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#define Maxn 2000003

using namespace std;

typedef long long int LL;

LL n,m,k,x,s,x1,s1;

LL a_short_time[Maxn] = {0};
LL a_cost[Maxn] = {0};

LL b_pro_num[Maxn] = {0};
LL b_cost[Maxn] = {0};

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m>>k>>x>>s;
    LL i = 1;
    LL ans = n*x;
    for(i = 1; i <= m; i++)
        cin >> a_short_time[i];
    a_short_time[0] = x;
    for(i = 1; i <= m; i++)
        cin >> a_cost[i];
    for(i = 1; i <= k; i++)
        cin >> b_pro_num[i];
    for(i = 1; i <= k; i++)
        cin >> b_cost[i];
    for(i = 0; i <= m; i++)
    {
        if(s >= a_cost[i])
        {
            LL s1 = s - a_cost[i];
            LL l = 0,r = k;
            while(l < r)
            {
                LL mid = (l + r) / 2;
                if(b_cost[mid] <= s1)
                {
                    if(b_cost[mid+1] > s1)
                    {
                        l = mid;
                        break;
                    }
                    else
                        l = mid + 1;
                }
                else
                    r = mid;
            }
            ans = min(ans,a_short_time[i]*(n-b_pro_num[l]));
        }
    }
    cout << ans;
    return 0;
}


Comments

Submit
0 Comments
More Questions

1371C - A Cookie for You
430B - Balls Game
1263A - Sweet Problem
1332B - Composite Coloring
254A - Cards with Numbers
215A - Bicycle Chain
1288B - Yet Another Meme Problem
1201C - Maximum Median
435A - Queue on Bus Stop
1409B - Minimum Product
723B - Text Document Analysis
1471C - Strange Birthday Party
1199A - City Day
1334A - Level Statistics
67B - Restoration of the Permutation
1734A - Select Three Sticks
1734B - Bright Nice Brilliant
357B - Flag Day
937A - Olympiad
1075A - The King's Race
1734C - Removing Smallest Multiples
1004C - Sonya and Robots
922A - Cloning Toys
817A - Treasure Hunt
1136B - Nastya Is Playing Computer Games
1388A - Captain Flint and Crew Recruitment
592B - The Monster and the Squirrel
1081A - Definite Game
721C - Journey
1400A - String Similarity